﻿//https://leetcode.cn/problems/reorder-list/description/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
////快慢指针找中间 + 逆序
class Solution {
public:
    //快慢指针找中间 + 逆序
    ListNode* firstOfHalfend(ListNode* head)
    {
        ListNode* fast = head, * slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = nullptr, * cur = head;
        while (cur)
        {
            ListNode* next = cur->next;

            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    void reorderList(ListNode* head1) {
        ListNode* tail = firstOfHalfend(head1);
        ListNode* head2 = reverse(tail->next);
        tail->next = nullptr;

        ListNode* cur2 = head2;
        ListNode* cur1 = head1;
        ListNode* pos = new ListNode;
        while (cur1) {
            ListNode* cur1Next = cur1->next;

            pos->next = cur1;
            pos = pos->next;
            cur1->next = cur2;
            pos = pos->next;

            cur1 = cur1Next;
            if (cur2 == nullptr)break;
            cur2 = cur2->next;
        }

    }
};
//答案
class Solution
{
    public :
    void reorderList(ListNode* head)
    {
        // 处理边界情况
        if (head == nullptr || head->next == nullptr || head->next->next == nullp
            // 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥）
            ListNode * slow = head, *fast = head;
            while (fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            } /
                / 2. 把 slow 后⾯的部分给逆序 - 头插法
                    ListNode * head2 = new ListNode(0);
                    ListNode* cur = slow->next;
                    slow->next = nullptr; // 注意把两个链表给断开
                while (cur)
                {
                    ListNode* next = cur->next;
                    cur->next = head2->next;
                    head2->next = cur;
                    cur = next;
                } /
                    / 3. 合并两个链表 - 双指针
                    ListNode * ret = new ListNode(0);
                ListNode* prev = ret;
                ListNode* cur1 = head, * cur2 = head2->next;
                while (cur1)
                {
                    // 先放第⼀个链表
                    prev->next = cur1;
                    cur1 = cur1->next;
                    prev = prev->next;
                    // 再放第⼆个链表
                    if (cur2)
                    {
                        prev->next = cur2;
                        prev = prev->next;
                        cur2 = cur2->next;
                    }
                } d
                    elete head2;
                delete ret;
    }
};